package GreedyAlgorithmPackage;

import org.junit.jupiter.api.Test;

/**
 * @author Lzm
 * @version 1.0
 */
public class monotoneIncreasingDigits_ {
  int n = 0;
  @Test
  public void monotoneIncreasingDigitsTest(){
    int n = 332;
    System.out.println(monotoneIncreasingDigits(n));

  }

  // 从后向前遍历, 当遇到当前位数字比前一位数字小, 就让当前位数变为9,前一位-1
  // 从后向前遍历, 当遇到当前位数字比前一位数字小, 就记录下来, 令前一位-1, 遍历解释后, 令记录下来之后的所有数都变成9
  public int monotoneIncreasingDigits(int n) {
    String[] strings = (n + "").split("");
    int start = strings.length;
    for (int i = strings.length - 1 ; i > 0 ; i--){
      if (Integer.parseInt(strings[i]) < Integer.parseInt(strings[i - 1])){
        start = i;
        strings[i - 1] = (Integer.parseInt(strings[i - 1]) - 1) + "";
      }
    }
    for (int i = start ; i < strings.length ; i ++){
      strings[i] = "9";
    }
    return Integer.parseInt(String.join("",strings));
  }
}
